package com.ys.HashMap模拟实现;

/**
 * 描述:
 *
 * @author CodeYang
 * @version 2020/12/26 17:05
 */
public class HashMap <K,V>{
    /**
     * 哈希表: 数组 + 链表 或者称呼为 节点链表
     */
    private Node<K,V>[] table;

    public HashMap() {
        this(16);
    }

    public HashMap(int cap){
        // 处理 cap 不合法
        if (cap<0){
            throw  new IllegalArgumentException("cap 不合法:cap:"+cap);
        }
        // 泛型 只能用在声明时,不能用在实例化
        table = new Node[cap];
    }

    /**
     * 添加 key -value 对象
     * 先判断一下要存储内容的key值是否为null，如果key为null，则将该内容存储到table数组的第一个位置。
     * @param key
     * @param value
     */
    public void put(K key,V value){
        // 情况一; 处理key 为null 核心:
        //如果key为null，存储位置为table[0]或table[0]的冲突链上
        //    1: 判断 key 为null这个key-value 是否在table[0] 这个链表中
        //    2; 链表不存在 ,直接更新为首节点   把 table[0]= 新元素节点对象(k,v)
        if (key == null){
            // 当数组的第一个元素已经存在一个链表了,存在key 为null 覆盖值
            for(Node<K,V> node = table[0];node!=null;node=node.next){
                if (null == node.key){
                    // 覆盖值
                    node.value = value;
                }
            }
            // 到此处
            // 数组中第一个元素不存在key为null,直接更新为首节点
            table[0] = new Node<>(0,key,value,null);
            return;
        }
        // 情况二; key 不为null
        // 1: 计算key的hash 值
        int hash = key.hashCode();
        // 获得键值对 应该存储的节点的 数组index 位置
        int index = hash % table.length;
        // 2: 遍历 数组[index] 链表中的key 值,如果传入key 与遍历的key相同,则覆盖value
        // 1: 声明 空节点用于辅助遍历: 为我们要put进入的这个数组的首节点对象地址值
        // 2: 循环遍历,每一次都遍历下一个,链表遍历方式 next temp= temp.next
        // 3: 结束条件,遍历到尾节点之前 temp !=null, 因为单链表尾节点next 为null
        for (Node<K,V> temp = table[index]; temp!=null; temp= temp.next ) {
            // 比对效率提升;
            // 1 temp.hash == hash 为假 && 右边不执行
            // 2 key == temp.key 地址值指向  key.equals(key) 成员变量值内容的判断
            if (temp.hash == hash &&(key == temp.key || key.equals(key))){
                // 覆盖操作
                temp.value = value;
                return;
            }
        }
        //3 执行到此处,证明 key 未重复
        // 直接把 node 插入到 链表的最前面 就是让node的next 指向当单链表的开始==table[index]
        Node<K,V> node = new Node<>(hash,key,value,table[index]);
        // 更新 首节点
        table[index] = node;

    }

    /**
     * 根据key获得value
     *
     * @param key
     * @return 如果key在map中存在,返回 对应value 不存在返回null
     */
    public V get(K key){
        // key 为null
        if (key == null)
        {
             // 1: 数组已经存在有了 null key 对象 从table[0] 中遍历key为null 的值
            for (Node<K,V> temp = table[0]; temp!=null ; temp = temp.next) {
                if (null == temp.key) {
                    return temp.value;
                }
            }
            // 没找到
            return null;
        }
        // key 不为null 返回
        // 计算哈希算法
        int hash = key.hashCode();
        // 计算数组的 index 坐标
        //int index = hash %  table.length  相等
        int index = hash & (table.length -1);
        for (Node<K,V> temp =table[index]; temp != null ; temp=temp.next) {
            // 在哈希表中找到了 返回对应的value
            if (hash == temp.hash && (key == temp.key || key.equals(key))){
                return temp.value;
            }
        }
        // 执行到此处,证明没找到
        return null;

    }




    /**
     *  Node 类,链表
     * @param <K> key
     * @param <V> value
     */
    private static class Node<K,V>{
        /**
         * 存储哈希值
         * final 修饰未直接赋值,要在构造方法去赋值
         */
       private   final  int   hash;
        /**
         * 存储key
         */
       private K key;
        /**
         * 存储value
         */
       private V value;
        /**
         * 指向下一个节点,next 指针
         */
       private Node<K,V> next;

        /**
         * 有参构造方法 初始化节点对象
         * @param hash
         * @param key
         * @param value
         * @param next
         */
        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

}
